/*************************************************************************
	> File Name: nixudui.cpp
	> Author: 赵江坤
	> Mail: zhaojk90@gmail.com 
	> Created Time: 2013年04月04日 星期四 23时00分01秒
 ************************************************************************/

#include<iostream>
using namespace std;
int merge(int *a,int p,int r,int q);
int merge_sort(int *a,int p,int q);
int main()
{
	int a[]={1,3,7,8,2,4,6,5};
	int n=merge_sort(a,0,7);
	for(int i=0;i<8;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	cout<<"逆序对为: "<<n<<endl;
}



int merge_sort(int *a,int p,int q)
{
	int r=(p+q)/2;
	int count=0;
	if(p<q)
	{
	
	count+=merge_sort(a,p,r);
	count+=merge_sort(a,r+1,q);
	count+=merge(a,p,r,q);
	}
	return count;

}
int merge(int *a,int p,int r,int q)
{
	int n1=r-p+1,n2=q-r,i;
	int *L=new int[n1],*R=new int[n2];
	for(i=0;i<=n1;i++)
		L[i]=a[p+i];
	for(i=0;i<n2;i++)
		R[i]=a[r+i+1];
	int j=0,k=0,count=0;
	for(i=p;i<q+1;i++)
	{
		if(j<n1 && k<n2)
		{
			if(L[j]<=R[k]){

				a[i]=L[j];
				j++;
			}else{
				
				a[i]=R[k];
				count+=n1-j;
				k++;
			}
		}else{
			if(j==n1)
			{
			a[i]=R[k];k++;
			}else{
			a[i]=L[j];
		//	count+=n1-j;
			j++;
			}
		}

	}
	return count;
}
